1. Field of the invention
The present invention relates generally to a method for protecting information stored on a disk drive and, in particular, to a method of performing Exclusive OR (XOR) operations in a hard disk drive controller.
2. Description of Related Art
A block diagram of a typical disk drive is shown in FIG. 1. Disk drive 150 has a hard disk controller 130 connected to a host interface bus 120. A buffer memory 100 and a microprocessor 160 are connected to hard disk controller 130. A read/write channel 140 further connects hard disk controller 130 to disk 110.
Buffer memory 100 is primarily used as a speed matching FIFO for data transferred between disk 110 and host interface bus 120. For data written from host interface bus 120 to disk 110 ("write data"), hard disk controller 130 fetches the data from host interface bus 120 and writes it to buffer memory 100, which is typically a Dynamic Random Access Memory (DRAM). Hard disk controller 130 fetches the write data from buffer memory 100 and writes the data at the appropriate location on disk 110 through read/write channel 140.
For data read from disk 110 to host interface bus 120 ("read data"), hard disk controller 130 fetches the read data from the appropriate location on disk 110, and writes the read data to buffer memory 100. The data is then read from buffer memory 100 and sent to host interface bus 120.
Note that for both read and write operations, transfers to/from host interface bus 120 and to/from disk 110 typically overlap to reduce operation latency. Thus, buffer memory 100 must have sufficient bandwidth to handle concurrent disk and host transfers.
In recent years, advances in processor performance have far outpaced advances in I/O performance. In addition, the requirement to have 100% on-line protection of user data has become more prevalent. Several subsystem architectures have been developed to deal with these problems. One of the most prevalent techniques has been to incorporate a Redundant Array of Inexpensive Drives (RAID) architecture into the subsystems. RAID is also sometimes said to stand for a Redundant Array of Independent Drives.
RAID architectures are based on storing data on multiple different disk drives, such as disk drive 100, to prevent the loss of user data due to a disk drive failure. By having data stored on more than one disk drive, loss of data caused by the failure of an individual disk drive can be prevented by restoring the data using information on the other disk drives.
Several levels of RAID architectures have been defined, each reflecting a particular balance of data security vs. efficiency of storage space allocation. For example, a RAID 1 architecture simply mirrors the data stored on one disk drive on a second disk drive. RAID 1, therefore, provides a high level of data security, since all the data is stored on two independent disk drives, but uses considerable space, effectively doubling the amount of storage space required.
A RAID 5 architecture, on the other hand, rather than duplicating all the data on one disk drive, simply stores correction code data on a separate disk drive and so improves the storage efficiency. Thus, a RAID 5 architecture ensures adequate data security, i.e. it can recover from a disk drive failure, with minimal use of additional storage space.
As is known to those of skill in the art, a RAID 5 architectures utilizes stripes of data on a plurality of disk drives and uses an Exclusive OR (XOR) function of the stripes of data to generate parity data that is used in the data recovery process and is stored on the separate disk drive. Consequently, the performance of a RAID 5 architecture is related to the performance of the XOR function.
In a typical RAID 5 write operation, the new data is written to the buffer memory from a computer bus, and the old data that will be overwritten is retrieved and stored in the buffer memory. The new data and the old data are simultaneously applied byte-by-byte to an XOR function to generate a bit mask that has a one in every bit that has changed in the new data. The old parity information for the data that is being overwritten is retrieved from the parity disk drive and the bit mask and the old parity data are simultaneously applied byte-by-byte to the XOR function to generate new parity data. The new data and the new parity data are stored in the RAID 5 system.
Regenerating data, that was on a failed disk drive, also requires multiple XOR operations of data from two different data sources. Thus, management of a RAID 5 system requires performing a byte-by-byte XOR operation on data from two different sources. Herein, the sources are referred to as source S1 and source S2 and the resultant XOR data is referred to as parity data X. Sources S1 and S2 are any two of host interface bus 120, disk 110 or buffer memory 100. The destination of parity data X is either disk 110 or host interface bus 120. Additionally, some XOR operations require source S1 to be saved for transfer to a different destination after parity data X is generated.
Since host interface bus 120 and disk 110 operate at different transfer rates, the XOR cannot be performed by concurrently reading data directly from the sources. As a result, one of the sources must first be transferred to buffer 100 to perform the XOR in the hard disk controller 130. Once source S1 or source S2 is transferred to buffer memory 100, the data sources for the XOR circuit 200 are buffer memory 100 and either host interface bus 120 or disk 110, as shown in FIGS. 2A-2B.
Typically, a block of memory locations 320 is allocated for the source data in buffer memory 100 and a second block of memory locations 310 is allocated for storing output parity data X after it is generated, as shown in FIG. 3. Blocks 310 and 320 both consist of n bit sets labelled 0 through n-1.
During the XOR operation data is therefore read from memory locations 320, XORed with the data read from the second source 330 and written back to memory locations 310. The speed with which this operation is conducted clearly affects the performance of the hard drive. Several methods can be used to conduct this operation.
In the simplest method, known as single-access XOR, each bit set is read from buffer memory 100 as the corresponding bit set is received from second source 330, the two bit sets are XORed by XOR circuit 200 and the result is written back to buffer memory 100. That is, hard disk controller 130 sequentially alternates between a single-bit-set read access and a single-bit-set write access of buffer memory 100, as shown in FIG. 4. This scheme uses two pointers into buffer memory 100, one pointer for the source data and one pointer for the XORed data. The number of clock cycles needed to XOR each bit set is equal to the number of clock cycles required to read and write a bit set. For example, in the case of the AIC-8321 hard disk controller, that is available from Adaptec, Inc. of Milpitas, Calif., the XOR throughput is 12 clock cycles per bit set (6 cycles for the read and 6 cycles for the write).
DRAMs, however, allow for an optimal access rate when data is accessed in bursts of a certain size. For example, in the case of the AIC-8321, with a standard Fast Page Mode DRAM, it takes 20 clock cycles to read or write a burst of 8 bit sets. Therefore, if the XOR were executed on blocks of 8 bit sets, it would take 40 cycles to XOR each 8 bit set block (20 cycles for the read and 20 cycles for the write), for an average of 5 cycles per bit set, as shown in FIG. 5.
However, to implement this scheme, known as burst XOR, on existing hard disk controllers such as the AIC-8321, additional hardware is required for storing a full burst of data (register file, RAM, etc.).
There is thus a need for a method to perform RAID 5 XOR operations which allows for faster execution, without requiring extensive hardware to be added to existing hard disk controllers.